class Pair {
    constructor(key, val) {
        this.key = key
        this.val = val
    }
}

class HasMapOpenAddressing {
    #size; // 键值对数量
    #capacity; // 哈希表容量
    #loadThres; // 触发扩容的负载因子阈值
    #extendRatio; // 扩容倍数
    #buckets; // 桶数组
    #TOMBSRONE; // 删除标记

    constructor() {
        this.#size = 0
        this.#capacity = 4
        this.#loadThres = 2.0 / 3.0
        this.#extendRatio = 2
        this.#buckets = new Array(this.#capacity).fill(null)
        this.#TOMBSRONE = new Pair(-1 , '-1') // 删除标记
    }

    // 哈希函数
    #hasFactor(key) {
        return key % this.#capacity
    }

    // 负载因子
    #loadFactior() {
        return this.#size / this.#capacity
    }

    // 搜索 key 对应的桶索引
    #findBucket(key) {
        let index = this.#hasFactor(key)
        let firstTombstone = -1
        // 线性探测，当遇到空桶时跳出
        while(this.#buckets[index] !== null) {
            // 若遇到 key，返回对应桶的索引
            if(this.#buckets[index].key === key) {
                // 若之前遇到了删除标记，则将键值对移动至该索引处
                if(firstTombstone !== -1) {
                    this.#buckets[firstTombstone] = this.#buckets[index]
                    this.#buckets[index] = this.#TOMBSRONE
                    return firstTombstone
                }
                return index;
            }
            // 记录遇到的首个删除标记
            if(firstTombstone === -1 && this.#buckets[index] === this.#TOMBSRONE) {
                firstTombstone = index
            }
            index = (index + 1) % this.#capacity
        }
        // 若 key 不存在，则返回添加点的索引
        return firstTombstone === -1 ? index : firstTombstone
    }

    // 查询操作
    get(key) {
        // 搜索 key 对应的桶索引
        const index = this.#findBucket(key)
        // 若找到键值对，则返回对应 val
        if(this.#buckets[index] !== null && this.#buckets[index] != this.#TOMBSRONE) {
            return this.#buckets[index].val
        }
        // 若键值对不对，则返回 null
        return null
    }

    put(key, val) {
        if(this.#loadFactior() > this.#loadThres) {
            this.#extend()
        }
        const index = this.#findBucket(key)
        if(this.#buckets[index] !== null && this.#buckets[index] !== this.#TOMBSRONE) {
            this.#buckets[index].val = val
            return
        }
        // 若键值对不存在，则添加该键值对
        this.#buckets[index] = new Pair(key, val)
        this.#size++
    }

    remove(key) {
        const index = this.#findBucket(key)
        if(this.#buckets[index] !== null && this.#buckets[index] !== this.#TOMBSRONE) {
            this.#buckets[index]  = this.#TOMBSRONE
            this.#size--
        }
    }

    #extend() {
        // 暂存原哈希表
        const bucketsTmp = this.#buckets
        this.#capacity *= this.#extendRatio
        this.#size = 0
        for(const pair of bucketsTmp) {
            if(pair !== null && pair !== this.#TOMBSRONE) {
                this.put(pair.key, pair.val)
            }
        }
    }

    print() {
        for (const pair of this.#buckets) {
            if(pair === null) {
                console.log('null')
            } else if(pair === this.#TOMBSRONE) {
                console.log('TOMBSRONE')
            } else {
                console.log(`${pair.key} -> ${pair.val}`)
            }
        }
    }
}